Data Structure

해시

해시법 💬 해시법은 데이터를 저장할 위치를 간단한 연산으로 구하는 것으로, 검색뿐만 아니라 추가, 삭제도 효율적으로 수행할 수 있다. 💬 정렬된 배열에 새로운 값을 추가하기 위해서는 아래의 과정이 필요하다. 💬 배열의 키 값을 배열의 요솟수 13으로 나눈 나머지로 다시 나눈 나머지로 정리하면 아래와 같다. 💬 이렇게 표에 정리한 값을 해시 값이라고 하며, 해시 값은 데이터에 접근할 때 사용한다. 💬 해시 값이 인덱스가 되도록 원래의 키 값을 저장한 배열이 아래의 해시 테이블이다. 💬 이제 배열에 새로운 값 35를 추가할 때, 다른 배열 요소들을 뒤로 옮기지 않아도 된다. 💬 이와 같이 키 값(35)를 가지고 해시 값(9)를 만드는 과정을 해시 함수라고 하며, 해시 테이블의 각 요소를 버킷이라고 한다. 충..

트리

트리 트리 관련 용어 💬 순서 트리와 무순서 트리 ◽ 형제 노드의 순서가 있는지 없는지에 따라 트리를 구분할 수 있다. 순서 트리 탐색 너비 우선 탐색 💬 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 검색하고 한 레벨에서의 검색이 끝나면 다음 레벨로 내려간다. 💬 A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L 깊이 우선 탐색 💬 리프까지 내려가면서 검색하는 것을 우선순위로 하는 탐색 방법이다. 💬 리프에 도달해 더 이상 검색을 진행할 곳이 없는 경우에는 부모에게 돌아간 후, 순차적으로 자식 노드로 탐색을 이어간다. 전위 순회 (Preorder) 💬 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식 💬 A -> B ->D ->H ->E ->I -> J -..

연결 리스트

포인터로 연결 리스트 만들기 public class LinkedList { // 노드 class Node { private E data; // 자기 자신의 데이터 private Node next; // 다음 노드를 가리키는 포인터 // 생성자 Node(E data, Node next) { this.data = data; this.next = next; } } private Node head; // 머리 노드를 가리킨다. private Node crnt; // 현재 선택한 노드를 가리킨다. public LinkedList() { head = crnt = null; } } 💬 head는 머리 노드에 대한 참조이지, 머리 노드 그 자체가 아님을 주의해야 한다. 💬 비어있는 연결 리스트는 노드도 없고, head..

문자열 검색

브루트-포스법 💬 주어진 텍스트에 검색하고자하는 패턴 문자열이 포함되어 있는지를 확인하는 문자열 검색 방법 💬 텍스트와 패턴에 문자열을 하나씩 검색하는 포인터를 설정하여 하나씩 이동하면서 같은지 검사한다. 💬 검사할 때마다 문자열이 다를 경우, 텍스트 포인터를 하나씩 늘려가며 검사한다. 💬 하지만, 검사를 진행한 위치를 기억하지 못하므로 효율이 좋지 않은 알고리즘이다. class BFmatch { // 브루트-포스법으로 문자열을 검색하는 메서드 static int bfMatch(String txt, String pat) { int pt = 0; // txt 커서 int pp = 0; // pat 커서 while (pt != txt.length() && pp != pat.length()) { if (txt..

배열로 집합 만들기

public class IntSet { private int max; // 집합의 최대 개수 private int num; // 집합의 요소 개수 private int[] set; // 집합 본체 // 생성자 public IntSet(int capacity) { num = 0; max = capacity; try { set = new int[max]; // 집합 배열 생성 } catch (OutOfMemoryError e) { max = 0; // 배열 생성 실패 } } // 집합의 최대 개수 public int capacity() { return max; } // 집합의 요소 개수 public int size() { return num; } // 집합에서 n을 검색(index 반환) public int..

재귀 알고리즘

팩토리얼 구하기 class Factorial { static int factorial(int n) { if (n > 0) return n * factorial(n - 1); else return 1; } } 유클리드 호제법으로 최대 공약수 구하기 class EuclidGCD { static int gcd(int x, int y) { if (y == 0) return x; else return gcd(y, x % y); } } 재귀 알고리즘 분석 💬 주어지는 알고리즘을 이용하여 원리를 파악하고, 재귀 알고리즘을 비재귀 알고리즘으로 풀어보자. class Recur { // 재귀 함수 static void recur(int n) { if (n > 0) recur(n - 1); System.out.println..

큐

큐란? ◽ 데이터를 일시적으로 쌓아 두기 위한 자료구조 ◽ 데이터 입력과 출력 순서는 선입선출(FIFO) ◽ 배열로 큐 만들기 ◽ 인큐 시간 복잡도 : O(1) ◽ 디큐 시간 복잡도 : O(n) : 꺼낸 다음 요소부터 모든 요소들을 앞으로 한 칸씩 모두 당겨야 함 ◽ 링 버퍼로 큐 만들기 ◽ 배열의 처음과 끝이 연결되어 있는 자료구조 링 버퍼로 큐 구현하기 본체 만들기 public class IntQueue { private int max; // 큐의 용량 private int front; // 첫 번째 요소 커서 private int rear; // 마지막 요소 커서 private int num; // 현재 데이터 수 private int[] que; // 큐 본체 // 실행 시 예외 : 큐가 비어 있..

스택

스택이란? ◽ 데이터를 일시적으로 저장하기 위해 사용하는 자료구조 ◽ 데이터의 입력과 출력 순서는 후입선출(LIFO) 스택 구현하기 본체 만들기 class IntStack { int max; // 스택 용량 int ptr; // 스택 포인터 int[] stk; // 스택의 본체 // 실행 시 예외 : 스택이 비어 있음 public class EmptyIntStackException extends RuntimeException { public EmptyIntStackException() { } } // 실행 시 예외 : 스택이 가득 참 public class OverflowIntStackException extends RuntimeException { public OverflowIntStackExcepti..

검색

선형 검색 알고리즘 1 class MainClass { static int seqSearch(int[] a, int n, int key) { int i = 0; while (true) { if (i == n) return -1; // 검색 실패 (-1을 반환) if (a[i] == key) return i; // 검색 성공 (인덱스를 반환) i++; } } } // a : 검색할 배열 // n : 배열의 크기 // key : 찾을 값 알고리즘 2 class MainClass { static int seqSearch(int[] a, int n, int key) { for (int i = 0; i < n; i++) { if (a[i] == key) return i; return -1; } } 알고리즘 3 c..

배열

자료구조 ◽ 데이터 단위와 데이터 자체 사이의 물리적 또는 논리적 관계 ◽ 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법 배열 int[] a; // 선언 a = new int[5]; // 생성 ◽ 배열을 생성하고 초기화를 하지 않을 경우, 자동으로 0으로 초기화된다. 배열의 복제 int[] a = {1, 2, 3, 4, 5}; int[] b = a.clone(); // 복제 배열의 최댓값 class MainClass { static int maxOf(int[] a) { int max = a[0]; for (int i = 1; i max) max = a[i]; return max; } } 난수의 생성 Random rand = new Random..